I. Field of the Invention
The present invention relates to communications. More particularly, the present invention relates to a novel and improved method and apparatus for detecting a pilot signal with a programmable matched filter searcher.
II. Description of the Related Art
Pseudorandom noise (PN) sequences are commonly used in direct sequence spread spectrum communication systems such as that described in the IS-95 over the air interface standard and its derivatives such as IS-95-A and ANSI J-STD-008 (referred to hereafter collectively as the IS-95 standard) promulgated by the Telecommunication Industry Association (TIA) and used primarily within cellular telecommunications systems. The IS-95 standard incorporates code division multiple access (CDMA) signal modulation techniques to conduct multiple communications simultaneously over the same RF bandwidth. When combined with comprehensive power control, conducting multiple communications over the same bandwidth increases the total number of calls and other communications that can be conducted in a wireless communication system by, among other things, increasing the frequency reuse in comparison to other wireless telecommunication technologies. The use of CDMA techniques in a multiple access communication system is disclosed in U.S. Pat. No. 4,901,307, entitled xe2x80x9cSPREAD SPECTRUM COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERSxe2x80x9d, and U.S. Pat. No. 5,103,459, entitled xe2x80x9cSYSTEM AND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEMxe2x80x9d, both of which are assigned to the assignee of the present invention and incorporated by reference herein.
FIG. 1 provides a highly simplified illustration of a cellular telephone system configured in accordance with the use of the IS-95 standard. During operation, a set of subscriber units 10a-d conduct wireless communication by establishing one or more RF interfaces with one or more base stations 12a-d using CDMA modulated RF signals. Each RF interface between a base station 12 and a subscriber unit 10 is comprised of a forward link signal transmitted from the base station 12, and a reverse link signal transmitted from the subscriber unit. Using these RF interfaces, a communication with another user is generally conducted by way of mobile telephone switching office (MTSO) 14 and public switch telephone network (PSTN) 16. The links between base stations 12, MTSO 14 and PSTN 16 are usually formed via wire line connections, although the use of additional RF or microwave links is also known.
Each subscriber unit 10 communicates with one or more base stations 12 by utilizing a rake receiver. A RAKE receiver is described in U.S. Pat. No. 5,109,390 entitled xe2x80x9cDIVERSITY RECEIVER IN A CDMA CELLULAR TELEPHONE SYSTEMxe2x80x9d, assigned to the assignee of the present invention and incorporated herein by reference. A rake receiver is typically made up of one or more searchers for locating direct and multipath pilot from neighboring base stations, and two or more fingers for receiving and combining information signals from those base stations. Searchers are described in co-pending U.S. patent application Ser. No. 08/316,177, entitled xe2x80x9cMULTIPATH SEARCH PROCESSOR FOR SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEMSxe2x80x9d, filed Sep. 30, 1994, assigned to the assignee of the present invention and incorporated herein by reference.
Inherent in the design of direct sequence spread spectrum communication systems is the requirement that a receiver must align its PN sequences to those of the base station. In IS-95, each base station and subscriber unit uses the exact same PN sequences. A base station distinguishes itself from other base stations by inserting a unique offset in the generation of its PN sequences. In IS-95 systems, all base stations are offset by an integer multiple of 64 chips. A subscriber unit communicates with a base station by assigning at least one finger to that base station. An assigned finger must insert the appropriate offset into its PN sequence in order to communicate with that base station. It is also possible to differentiate base stations by using unique PN sequences for each rather than offsets of the same PN sequence. In this case, fingers would adjust their PN generators to produce the appropriate PN sequence for the base station to which it is assigned.
Subscriber units locate base stations by utilizing searchers. FIG. 2 depicts a common type of serial correlator used for searching in a subscriber unit. This searcher is described in U.S. Pat. No. 5,644,591, entitled xe2x80x9cMETHOD AND APPARATUS FOR PERFORMING SEARCH ACQUISITION IN A CDMA COMMUNICATIONS SYSTEMxe2x80x9d, issued Jul. 1, 1997, assigned to the assignee of the present invention and incorporated herein by reference.
In FIG. 2, antenna 20 receives a signal comprising pilot signal transmissions from one or more base stations. The signal is downconverted and amplified in receiver 21, which generates an in-phase (I) and quadrature (Q) component of the received signal and delivers them to despreader 22. I and Q PN sequence generator 23 produces the proper I and Q PN sequences for a candidate offset as directed by searcher controller 27. Despreader 22 receives the I and Q PN sequences and despreads the I and Q received signals, passing the results to coherent accumulators 24 and 25. These accumulators integrate the amplitudes of the despread I and Q signals for a period of time specified by searcher controller 27. Coherent accumulators 24 and 25 sum the I and Q amplitudes for a period of time in which the phase of the incoming signal is approximately constant. The results are passed to energy calculation block 26 where the I and Q coherent accumulations are squared and summed. The result is accumulated in non-coherent accumulator 28. Non-coherent accumulator 28 is summing energies, and so the constant phase requirements of coherent accumulation do not apply. Energy is accumulated for a period of time as directed by searcher controller 27. The result is compared in threshold compare 29. Once the process is completed for the candidate offset programmed in I and Q PN sequence generator 23, searcher controller 27 directs a new candidate offset to be analyzed.
The searcher as just described has the advantage of great flexibility. Any number of coherent integrations, C, (within the limits of coherence time) may be performed on a candidate offset, and any number of non-coherent accumulations, M, may be performed. Any number of hypotheses to search, L, can be searched. The overall search time for a window of L hypotheses is then given by L*C*M. The drawback of this architecture is that each candidate is calculated in a serial manner. To reduce search time for given M and N requires that duplicative hardware be added.
FIG. 3 shows an alternative searcher architecture, commonly called a matched filter searcher. For a discussion of this method, see Simon, Omura, Scholtz and Levitt, SPREAD SPECTRUM COMMUNICATIONS HANDBOOK, pp. 815-822, McGraw-Hill, Inc., New York (1994).
An incoming signal is received at antenna 30 and passed to receiver 31 for downconversion and amplification. I and Q channels are then delivered to delay chains 36 and 38, respectively. Each delay chain contains N delay elements labeled DI1-DIN and DQ1-DQN. The output of each delay element is multiplied by a PN value loaded into tap value chains 35 and 37. The tap values are created with I and Q PN generators and loaded or hard coded into multiplication elements labeled PNI1-PNIN and PNQ1-PNQN. Note that in the simple case, the tap values include only 1 and xe2x88x921, so inverters (or negaters) take the place of actual multipliers. The associations of delay element outputs and tap values is shown in FIG. 3. The tap values are made up of a portion of the PN sequence which is used to correlate with the incoming data. The results of all the multiplications are delivered to adders 34 and 32, where they are summed. The results are then squared and summed to create an energy calculation in block 33, the result of which is compared in threshold compare 39. Whenever the energy result is high, it is likely that a base station pilot exists and its PN generators are aligned with the portion of the PN sequences contained in the tap elements. In a single pass of the time required to cycle through the entire PN sequence, every possible offset has an energy value calculated for it.
The benefits of this architecture include parallel calculations of N hypotheses such that a result is generated once for every cycle that the delay elements are updated. This architecture is optimal for the case where the number of hypotheses to be searched, L, is equal to the entire PN space, the number of coherent accumulations desired, C, is equal to the number of taps, N, and the number of non-coherent accumulations, M, is set to one. In this scanario, the total search time will be L+N (assuming that it requires N cycles to fill the delay elements with valid data). The delay elements may already contain valid data, and in any case N is typically much smaller than the PN space, so the search time is essentially related directly to L. Compare this with the time for the serial correlator searcher described above: L*C*M =L*C.
The maximum value for N is given by the coherence time. The matched filter portion of the searcher is essentially performing coherent accumulation of despread input signals. This is the same constraint for maximum C in the prior architecture. To increase the number of non-coherent accumulations requires adding memory storage to hold an intermediate calculation for every hypothesis to search, or L additional memory elements. The search time then for M greater than 1 is given by M*PN, where PN is the entire PN space.
The drawbacks to this architecture include lack of flexibility. It is optimal in hardware and time only for the limited circumstances set forth above. The hardware will be underutilized whenever desired C is less than the number of taps, N, or when the window to be searched, L, is less than the entire PN space and M is greater than one. In the first instance, the delay elements and PN taps exist in hardware whether or not they are used. In the second instance, the entire PN sequence must cycle through before a second non-coherent energy value is calculated. Furthermore, extra memory is required to store all the partial accumulations for each offset.
For some numerical examples, assume the PN space, PN, is 30000. We will compare a matched filter searcher as described with N=100 delay elements. Assume first that the desired search window also is 30,000, the desired C is 100, and the desired M is 1. These conditions are optimal for the matched filter searcher so its hardware will be fully utilized. The required search time will be L*M=30,000. The serial correlator searcher described above will also utilize its hardware efficiently, but its search time will be L*M*C=3,000,000, or 100 times greater. So to equal the speed performance with serial correlators, we would need to implement 100 of them in parallel. This would not be as efficient in area as the matched filter.
Now assume that with the same hardware we wish to search a window smaller than the entire PN sequence: L=1000. Assume further that coherent integrations, C, are set to only 25. Let M continue to be 1. This case demonstrates that the matched filter will not utilize all of its hardware efficiently, since xc2xe of it will be unused. The overall search time, 1000, is still lower than that of the serial correlator, 1000*25=25,000, but it is only 25 times faster. This assumes that the taps can be programmed in such a way as to take advantage of the reduced window sizexe2x80x94with fixed taps this is not the case and the search time will remain 30,000 which is actually slightly slower.
Finally, change only the assumption that M=5. Now the matched filter searcher will continue to operate at 25% hardware efficiency, and it will take M*PN or 150,000 cycles to search (and additional memory is required to store the L partial accumulations). The serial correlator will continue to operate at 100% hardware efficiency and will complete the task in L*C*M or 125,000. Clearly, as M is increased from 5, the performance gains of the serial correlator will only increase.
There are clear benefits in reducing search times ranging from initial acquisition to base-station handoff to multipath demodulation. There is a need in the art for a searcher which combines fast searching with flexibility and hardware efficiency.
A novel and improved method and apparatus for searching is described. In accordance with one embodiment of the invention, the searcher adds flexibility to the parallel computation features of a matched filter, allowing a variable number of coherent accumulations and a variable number of non-coherent accumulations to be performed at high speed for a wide range of search hypotheses in a resource efficient manner. This exemplary embodiment of the invention allows for parallel use of the matched filter structure in a time-sliced manner to search multiple windows. In addition, the searcher allows for optional independent Walsh decovering for each search window. The time-sharing approach allows for optional frequency searching of any offset.
In the exemplary embodiment, the I and Q channel data are despread utilizing a matched filter structure. The in-phase and quadrature amplitudes of the despreading delivered to coherent accumulators to sum for a programmable duration of time. The amplitude accumulations are squared and summed to produce an energy measurement. The energy measurement is accumulated for a second programmable time to perform non-coherent accumulation. The resulting value is used to determine the likelihood of a pilot signal at that offset.
Each matched filter structure comprises an N-value shift register for receiving data, a programmable bank of taps to perform despreading and optional Walsh decovering, and an adder structure to sum the resulting filter tap calculations. The matched filter structure can optionally be used in a time-sharing manner to search multiple windows as dictated by a multiplexor which supplies various streams of tap values for despreading (with optional Walsh decovering included in the tap values). In addition, an optional phase rotator can be added to apply multiplexed phase values to perform frequency searching. Every cycle the matched filter structure produces an intermediate calculation for a particular offset (with optional Walsh decovering and optional phase rotation) which includes N calculations based on the data in the shift register. Masking features may be used to allow a calculation using less than N values to be performed). The identification of certain features as optional does not imply that other features are required. Different aspects of the invention may be incorporated or omitted in different embodiments.